<?php
/**
 * User: helloJiu
 * Date: 2021/10/11
 * Time: 17:45
 */

namespace App\Algorithm\DP;

/**
 * 俄罗斯信封套娃
 * Class ELSEnvelope
 * @package App\Algorithm\DP
 */
class ELSEnvelope
{
    /**
     * 使用动态规划解决
     * https://leetcode-cn.com/problems/russian-doll-envelopes/
     * @param Integer[][] $envelopes
     * @return Integer
     */
    function maxEnvelopes($envelopes)
    {
        usort($envelopes, function ($v1, $v2) {
            return $v1[0] - $v2[0];
        });
        print_r($envelopes);

        $dp = [];
        $dp[0] = 1;
        // $dp 表示第i个能装的最大信封数

        for ($i = 1; $i < count($envelopes); $i++) {
            $dp[$i] = 1;
            for ($j = $i - 1; $j >= 0; $j--) {
                if($envelopes[$i][0] > $envelopes[$j][0] && $envelopes[$i][1] > $envelopes[$j][1]){
                    if($dp[$j] + 1 > $dp[$i]){
                        $dp[$i] = $dp[$j] + 1;
                    }
                }
            }
        }

        return max($dp);

    }
}